#include "TreeNode.h"
#include <vector>
using namespace std;

/**
 * 给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
 * 1.vin.length == pre.length
    2.pre 和 vin 均无重复元素
    3.vin出现的元素均出现在 pre里
    4.只需要返回根结点，系统会自动输出整颗树做答案对比
*/
TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
    if (preOrder.empty() || vinOrder.empty() ||
            preOrder.size() != vinOrder.size()) {
        return nullptr;
    }
    int root_val = preOrder[0];
    TreeNode* root = new TreeNode(root_val);
    int left_size = 0;
    for (int i = 0; i < vinOrder.size(); ++i) {
        if (vinOrder[i] == root_val) {
            left_size = i;
            break;
        }
    }
    // 根据根节点，分割左右子树，得到各自的中序遍历结果
    vector<int> vinOrderLeft;
    vector<int> vinOrderRight;
    for (int i = 0; i < vinOrder.size(); ++i) {
        if (i < left_size) {
            vinOrderLeft.push_back(vinOrder[i]);
        } else if (i > left_size) {
            vinOrderRight.push_back(vinOrder[i]);
        }
    }

    // 根据根节点，分割左右子树，得到各自的前序遍历结果
    vector<int> preOrderLeft;
    vector<int> preOrderRight;
    for (int i = 1; i < preOrder.size(); ++i) {
        if (i < left_size + 1) {
            preOrderLeft.push_back(preOrder[i]);
        } else {
            preOrderRight.push_back(preOrder[i]);
        }
    }

    root->left = reConstructBinaryTree(preOrderLeft, vinOrderLeft);
    root->right = reConstructBinaryTree(preOrderRight, vinOrderRight);
    return root;
}